package arithmetic.DP;


import org.junit.Test;

/**
 * DP（动态规划）：是寻找决策过程中最优方案过程，主要在背包问题，资源分配问题，最短路径问题和复杂系统可靠性问题等方面，有很多应用。
 * 动态规划算法通常用于求解具有某种最优性质的问题。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，
 * 先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，把多阶段问题变换为一系列相互联系的的单阶段问题，然后逐个加以解决。
 * 适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的
 */
public class DynamicPrograming {

    private static int arr[] = new int[100];

    /**
     * DAG最短路:
     * 给定一个城市的地图，所有的道路都是单行道，而且不会构成环。每条道路都有过路费，问您从S点到T点花费的最少费用。
     */
    @Test
    public void test1() {

    }

    /**
     * 最长上升子序列(LIS)
     */
    @Test
    public void test2() {

    }

    /**
     * Fibonacci 函数
     */
    public void test3() {

        Fibonacci(10);

    }


    public static int Fibonacci(int n) {
        if (n <= 2) {
            return 1;
        } else {
            if (arr[n] != 0) //判断是否计算过这个f(n)
                return arr[n];
            else {
                arr[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
                return arr[n];
            }
        }
    }
}
